package com.leetcode.二叉树;

import com.leetcode.二叉树.L104二叉树的最大深度.TreeNode;

/**
 * 给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。 完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，
 * 其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
 * 
 * 
 * @author LZF
 *
 */
public class L222完全二叉树的节点个数 {
	/**
	 * 单个节点也是满二叉树
	 * 完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。
	 * 对于情况一，可以直接用 2^树深度 - 1 来计算，注意这里根节点深度为1。
	 * 对于情况二，分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算。
	 * 
	 * 所以整体的基本步骤是，如果是满二叉树，就利用公式返回节点数。
	 * 如果不是，就判断左右子树是不是
	 * 因为，一个叶子节点也是满二叉树，所以最后肯定是可以找出所有的满二叉树的。
	 */
	public int countNodes(TreeNode root) {
//        return dfs(root);
		if(root == null) return 0;
		TreeNode left = root.left;
		TreeNode right = root.right;
		int leftH = 0;//左子树的高度
		int rightH = 0;//右子树的高度
		while(left != null) {
			left = left.left;
			leftH ++;
		}
		while(right != null) {
			right = right.right;
			rightH ++;
		}
		if(leftH == rightH) return (2 << leftH) - 1;//满二叉树
		return 1 + countNodes(root.left) + countNodes(root.right);//不是满二叉树，就普通递归，计算左右子树
    }
	//深度搜索没有利用到题目给的是完全二叉树，把每个节点都跑一遍了。
    public int dfs(TreeNode node){
    	if(node == null) return 0;
        return 1 + dfs(node.left) + dfs(node.right);
    }
	// 树的定义
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode() {
		}

		TreeNode(int val) {
			this.val = val;
		}

		TreeNode(int val, TreeNode left, TreeNode right) {
			this.val = val;
			this.left = left;
			this.right = right;
		}
	}
}
